# Problem 4
# 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
# What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

import unittest
import math
import Utility

     
def findAllPrimeFactors(N):
    result = []
    findPrimeFactor(2, N, result)
    return result

    
def findPrimeFactor(start, N, result):
    prime = 0
    found_prime = False
    for i in range(start, N + 1):
        if Utility.isPrime(i):
            prime = i
            break
    if prime == 0: # don't find prime
        return
    while N % prime == 0:
        N = int(N / prime)
        result.append(prime)
    findPrimeFactor(prime + 1, N, result)   
        

def findSmallestNumber(N):
    primeFactors = {}
    for i in range(2, N + 1):
        primeFactors[i] = findAllPrimeFactors(i)
    primes = Utility.getAllPrimes(N)
    factorCounts = {}
    for i in primes:
        max_count = 0
        for j in primeFactors.keys():
            count = primeFactors[j].count(i)
            if count > max_count:
                max_count = count
        factorCounts[i] = max_count
    result = 1
    for k in factorCounts.keys():
        result *= (k ** factorCounts[k])
    return result

  
class TestP005(unittest.TestCase):
    def test_findAllPrimeFactors(self):
        self.assertEqual(findAllPrimeFactors(2), [2])
        self.assertEqual(findAllPrimeFactors(8), [2, 2, 2])
        self.assertEqual(findAllPrimeFactors(10), [2, 5])
        self.assertEqual(findAllPrimeFactors(11), [11])
        self.assertEqual(findAllPrimeFactors(12), [2, 2, 3])         
        self.assertEqual(findAllPrimeFactors(13195), [5, 7, 13, 29])
        
    def test_findSmallestNumber(self):
        self.assertEqual(findSmallestNumber(10), 2520)
        self.assertEqual(findSmallestNumber(20), 232792560)
  

if __name__ == '__main__':
    P005 = unittest.TestLoader().loadTestsFromTestCase(TestP005)
    unittest.TextTestRunner(verbosity=2).run(P005)
    print 'the smallest positive number that is evenly divisible by all of the numbers from 1 to 20 [%d]' % findSmallestNumber(20)  
   